package com.hit.basmath.interview.we_meet.bytedance.news;

import java.util.ArrayList;
import java.util.List;

/**
 * 题目：输出给定数字下一个比它大的数字
 * <p>
 * 比如数字：1234， 输出 1243
 * 比如 1243，则输出 1324
 * 要求复杂度越优越好。
 * 测试case：
 * 输入：1346531
 * 输出：1351346
 */
public class NextBigNum {
    public static void main(String[] args) {
        int num = 1346531;
        String nextInt = findNextInt(num);
        System.out.println(nextInt);
    }

    private static String findNextInt(int num) {
        // 将该自然数放入数组
        List<Integer> nums = new ArrayList<Integer>();
        while (num % 10 > 0) {
            nums.add(0, num % 10);
            num = num / 10;
        }

        /**
         * 为了和原数接近，我们要保持高位不变，低位在最小范围内变换顺序
         * 从右向左寻找逆序区域的临界值
         */
        int criticalPoint = findCriticalPoint(nums);
        if (criticalPoint == -1) {
            // 不存在
            return "不存在";
        } else {
            /**
             * 存在
             * 就把临界值的前一个数和逆序区域中刚刚大于该数的数字交换位，
             * 然后把逆序区域变为顺序
             */
            return reorder(nums, criticalPoint);
        }
    }

    /**
     * 寻找逆序区域的临界值
     *
     * @param nums
     * @return
     */
    private static int findCriticalPoint(List<Integer> nums) {
        for (int i = nums.size() - 1; i > 0; i--) {
            if (nums.get(i) > nums.get(i - 1)) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 把逆序区域临界值的前一位和逆序区域中刚刚大于该数的数字交换位置,并把逆序区域变为顺序
     *
     * @param nums
     * @param index
     * @return
     */
    private static String reorder(List<Integer> nums, int index) {
        /**
         * 把逆序临界值的前一位和逆序区域中刚刚大于该数的数字交换位置
         * 记录临界值的前一个数
         */
        int left = nums.get(index - 1);

        // 循环逆序区域
        for (int i = nums.size() - 1; i >= index; i--) {
            int right = nums.get(i);
            if (left < right) {
                nums.set(index - 1, right);
                nums.set(i, left);
                break;
            }
        }

        // 把逆序区域变为顺序
        for (int i = index, j = nums.size() - 1; i < j; i++, j--) {
            int tmp = nums.get(i);
            nums.set(i, nums.get(j));
            nums.set(j, tmp);
        }
        return nums.toString();
    }
}
